import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int left = 0, right = 0, count = 0;
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for (int i =0; i < p.length(); i++) {
            hash1[p.charAt(i) - 'a']++;
        }
        for (; right < s.length(); right++) {
            hash2[s.charAt(right) - 'a']++;
            if (hash2[s.charAt(right)-'a'] <= hash1[s.charAt(right)-'a']) {
                count++;
            }
            while (right-left+1 > p.length()) {
                if (hash2[s.charAt(left)-'a'] <= hash1[s.charAt(left)-'a']) {
                    count--;
                }
                hash2[s.charAt(left)-'a']--;
                left++;
            }
            if (count == p.length()) {
                list.add(left);
            }
        }
        return list;
    }
}

/**
 * class Solution {
 *     public List<Integer> findAnagrams(String s, String p) {
 *         List<Integer> list = new ArrayList<>();
 *         int left = 0, right = 0, count = 0;
 *         int[] hash1 = new int[26];//
 *         int[] hash2 = new int[26];
 *         for (int i =0; i < p.length(); i++) hash1[p.charAt(i) - 'a']++;
 *         for (; right < s.length(); right++) {
 *             hash2[s.charAt(right) - 'a']++;
 *             if (hash2[s.charAt(right)-'a'] <= hash1[s.charAt(right)-'a']) count++;
 *             while (right-left+1 > p.length()) {
 *                 if (hash2[s.charAt(left)-'a']-- <= hash1[s.charAt(left)-'a']) count--;
 *                 left++;
 *             }
 *             if (count == p.length()) list.add(left);
 *         }
 *         return list;
 *     }
 * }
 */